/**
 * 插入排序
 */

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int> &v)
{
    int n = v.size();
    for (int i = 1; i < n; ++i)
    {
        int x = v[i];
        int j;
        for (j = i - 1; j >= 0; --j)
        {
            if (x < v[j])
            {
                v[j + 1] = v[j];
            } else {
                break;
            }
        }
        v[j + 1] = x;
    }
}

void printResult(vector<int> &v)  
{
    for (const auto &n : v) {
        cout << n << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> vTest = {1, 3, 45, 7, 2, 7, 3, 76};
    printResult(vTest);
    insertionSort(vTest);
    printResult(vTest);
    return 0;
}